/*
 * -------------------------------------------------------------------------
 * THE rxpoly LIBRARY, A LIBRARY FOR WORKING WITH REGEXPS IN POLYNOMIAL TIME
 * -------------------------------------------------------------------------
 * Copyright (C)	Matěj Korvas	2010
 * (email: matej.korvas@gmail.com)
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdlib.h>
#include <stdio.h>

/****** TYPES ******/
/* resources associated with an analyzed regular expression */
struct rxAnaRess_s;
typedef struct rxAnaRess_s rxAnaRess;

/* tuple of text indices */
typedef unsigned int t_idx;
struct begend_s {
	t_idx begin;
	t_idx end;
};
typedef struct begend_s begend;

/* array of `begend's */
struct begendArr_s {
	begend *mbrs;		// pointer to start of the array
	size_t limit;		// number of valid members (0..limit-1)
	size_t cap;			// size allocated (resp. cap*sizeof(begend));
									// If (cap==0), the memory at `mbrs' has not been allocated at 
									// all for this structure.
};
typedef struct begendArr_s begendArr;

/* type of the regular expression */
enum rxType_e { basic, extended };
typedef enum rxType_e rxType;

/* flags modifying interpretation of regular expressions */
typedef unsigned char rxFlags;

/* flags specifying the ordering of candidates */
typedef unsigned char rxCandOrdering;

/****** CONSTANTS ******/
/* invalid `begend' (meaning no matching substrings) */
begend invBegend;
/* `begend' signaling an exception */
begend excBegend;

/* `begendArr' signaling an exception */
begendArr excBegendArr;

/* flags - values */
/* whether substitutions shall be done globally (all possible disjunct) */
#define RF_GLOBAL		1
/* whether matching should be performed case-insensitively */
#define RF_ICASE		2
/* whether extended regular expressions shall be used instead of basic */
#define RF_BASIC		0
#define RF_EXTENDED	4
/* whether parentheses should be used for grouping only, not for reference in 
 * substituting */
#define RF_NOSUB		16

/* ordering flags - values */
/* By default, the candidates are sorted according to these criteria:
 * 		depth order (shallower is better),
 * 		left-right order (more to left is better),
 * 		greediness (greedy is better).	*/
#define RCO_DEFAULT	0
/* The direction of ordering (ascending vs. descending) can be switched using 
 * following flags (O = Order - nestedness, L = left-right order, 
 * G = greediness; the smaller value, the higher priority, if in ascending 
 * order) :	*/
#define RCO_O_ASC		0
#define RCO_O_DESC	32
#define RCO_L_ASC		0
#define RCO_L_DESC	64
#define RCO_G_ASC		128
#define RCO_G_DESC	0
/* This mask selects only the direction settings from `rxCandOrdering'. */
#define RCO_DIRMASK	224
/* The weights of ordering features (O/L/G) can be tuned using following 
 * switches (then they are weighted with decreasing weight with each next letter 
 * from the name of the flag; default is OLG) : */
#define RCO_OLG		0
#define RCO_OGL		1
#define RCO_LOG		2
#define RCO_LGO		3
#define RCO_GOL		4
#define RCO_GLO		5
/* This mask selects only the weights settings from `rxCandOrdering'. */
#define RCO_WMASK	7

/****** FUNCTIONS ******/
/* Compiles the regular expression into a form that is used internally. */
rxAnaRess *rxCompile( const wchar_t *const regex, rxFlags flags, rxCandOrdering rco );

inline void cleanRress( rxAnaRess *rress );
inline void freeRress( rxAnaRess *rress );

/* Tests for a match. */
int matches( const wchar_t *const text, const wchar_t *const regex,
										 rxFlags flags );
/* Tests for a match against a precompiled regex. */
int matchesPrec( const wchar_t *const text, rxAnaRess *const rress );

begend firstMatch( const wchar_t *const text, rxAnaRess *const rress );
begend nextMatch( rxAnaRess *const rress );
begend nextDisjunctMatch( rxAnaRess *const rress );
begendArr allMatches( const wchar_t *const text, const wchar_t *const regex,
											rxFlags flags, rxCandOrdering rco );
begendArr allMatchesPrec( const wchar_t *const text, rxAnaRess *const rress );
begendArr allDisjunctMatches( const wchar_t *const text, const wchar_t *const regex,
															rxFlags flags, rxCandOrdering rco );
begendArr allDisjunctMatchesPrec( const wchar_t *const text, rxAnaRess *const rress );
wchar_t *substitute( const wchar_t *text,
										 const wchar_t *regex,
										 const wchar_t *subst,
										 const rxFlags flags,
										 const rxCandOrdering rco );
